Q - Flowers
逆向きに考える
セグ木なりBITなりで高速化
考察
列から抜き取って単調増加にする…よりも、列に追加して単調増加にする…のほうが考えやすい
手元に予め持っておいて、単調増加になるように左から列に追加していくことを考える
DPっぽい配列dp[i] // 手元でi番目まで考えたときの列の総和の最大値を作る。で、追加していく時に「単調増加にするには、列の一番右がどの数字かが分かってないといけないな？」というお気持ちになります
なので、dp[i][j] // 手元でi番目まで考えて、なおかつ列の右端がjのときの列の総和の最大値とします
と思ったのですが、iの遷移をしていると間に合わなさそうなので、dp[i] // 列の右端がiのときの（以下略）とします
ここで、列に"14"を追加することを考えます
更新されるのはdp[14]になります。
列に14を追加する前の状態を考えると、列の右端が必ず13以下になっていることが分かります
列の右端が13以下になっている列で一番スコアが高いものに、14を追加すると良さそう…
ここで「列の右端が13以下になっている列で一番スコアが高いもの」を求めるのに、セグ木とかを使うことで高速化ができます
BITも使えます。BITめっちゃ実装楽なのでBIT使おうね。